//环绕字符串中唯一的子字符串
//测试链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/submissions/663700276/
public class FindSubstringInWraproundString {
    public int findSubstringInWraproundString(String ss) {
        int n = ss.length();
        char[] s = ss.toCharArray();
        // 1. 利⽤ dp 得到每⼀个位置为结尾的最⻓连续数组的⻓度
        int[] dp = new int[n];
        for (int i = 0; i < n; i++)
            dp[i] = 1;
        for (int i = 1; i < n; i++)
            if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] += dp[i - 1];
        // 2. 去重
        int[] hash = new int[26];
        for (int i = 0; i < n; i++)
            hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);

        // 3. 返回结果
        int sum = 0;
        for (int x : hash)
            sum += x;
        return sum;
    }
}
